{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Self Crossing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isSelfCrossing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #路径交叉"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>distance</code><em> </em>。</p>\n",
    "\n",
    "<p>从 <strong>X-Y</strong> 平面上的点&nbsp;<code>(0,0)</code>&nbsp;开始，先向北移动 <code>distance[0]</code> 米，然后向西移动 <code>distance[1]</code> 米，向南移动 <code>distance[2]</code> 米，向东移动 <code>distance[3]</code> 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。</p>\n",
    "\n",
    "<p>判断你所经过的路径是否相交。如果相交，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/14/selfcross1-plane.jpg\" style=\"width: 400px; height: 435px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>distance = [2,1,1,2]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/14/selfcross2-plane.jpg\" style=\"width: 400px; height: 435px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>distance = [1,2,3,4]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/14/selfcross3-plane.jpg\" style=\"width: 400px; height: 435px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>distance = [1,1,1,1]\n",
    "<strong>输出：</strong>true</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;=&nbsp;distance.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;distance[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [self-crossing](https://leetcode.cn/problems/self-crossing/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [self-crossing](https://leetcode.cn/problems/self-crossing/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,1,2]', '[1,2,3,4]', '[1,1,1,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3,n):\n",
    "            if distance[i]>=distance[i-2] and distance[i-1]<=distance[i-3]:\n",
    "                return True\n",
    "            if i>=4 and distance[i-1] == distance[i-3] and distance[i]+distance[i-4] == distance[i-2]:\n",
    "                return True\n",
    "            if i>=5 and distance[i-1] <= distance[i-3] and distance[i-2]>distance[i-4] and distance[i]+distance[i-4] >= distance[i-2] and distance[i-1]+distance[i-5]>=distance[i-3]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            # 第 1 类路径交叉的情况\n",
    "            if (distance[i] >= distance[i - 2]\n",
    "                    and distance[i - 1] <= distance[i - 3]):\n",
    "                return True\n",
    "\n",
    "            # 第 2 类路径交叉的情况\n",
    "            if i == 4 and (distance[3] == distance[1]\n",
    "                           and distance[4] >= distance[2] - distance[0]):\n",
    "                return True\n",
    "\n",
    "            # 第 3 类路径交叉的情况\n",
    "            if i >= 5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3]\n",
    "                           and distance[i] >= distance[i - 2] - distance[i - 4]\n",
    "                           and distance[i - 2] > distance[i - 4]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "\n",
    "        # 处理第 1 种情况\n",
    "        i = 0\n",
    "        while i < n and (i < 2 or distance[i] > distance[i - 2]):\n",
    "            i += 1\n",
    "\n",
    "        if i == n:\n",
    "            return False\n",
    "\n",
    "        # 处理第 j 次移动的情况\n",
    "        if ((i == 3 and distance[i] == distance[i - 2])\n",
    "                or (i >= 4 and distance[i] >= distance[i - 2] - distance[i - 4])):\n",
    "            distance[i - 1] -= distance[i - 3]\n",
    "        i += 1\n",
    "\n",
    "        # 处理第 2 种情况\n",
    "        while i < n and distance[i] < distance[i - 2]:\n",
    "            i += 1\n",
    "\n",
    "        return i != n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        if len(distance) < 4:\n",
    "            return False\n",
    "\n",
    "        for i in range(3, len(distance)):\n",
    "            if distance[i] >= distance[i-2] and distance[i-1] <= distance[i-3]:\n",
    "                return True\n",
    "            if i - 4 >= 0:\n",
    "                if distance[i-1] == distance[i-3] and distance[i] + distance[i-4] >= distance[i-2]:\n",
    "                    return True\n",
    "            if i - 5 >= 0:\n",
    "                if distance[i-2] >= distance[i-4] and distance[i] + distance[i-4] >= distance[i-2] and distance[i-1] + distance[i-5] >= distance[i-3] and distance[i-1] <= distance[i-3]:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "\n",
    "        # 处理第 1 种情况\n",
    "        i = 0\n",
    "        while i < n and (i < 2 or distance[i] > distance[i - 2]):\n",
    "            i += 1\n",
    "\n",
    "        if i == n:\n",
    "            return False\n",
    "\n",
    "        # 处理第 j 次移动的情况\n",
    "        if ((i == 3 and distance[i] == distance[i - 2])\n",
    "                or (i >= 4 and distance[i] >= distance[i - 2] - distance[i - 4])):\n",
    "            distance[i - 1] -= distance[i - 3]\n",
    "        i += 1\n",
    "\n",
    "        # 处理第 2 种情况\n",
    "        while i < n and distance[i] < distance[i - 2]:\n",
    "            i += 1\n",
    "\n",
    "        return i != n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            # 第 1 类路径交叉的情况\n",
    "            if (distance[i] >= distance[i - 2]\n",
    "                    and distance[i - 1] <= distance[i - 3]):\n",
    "                return True\n",
    "\n",
    "            # 第 2 类路径交叉的情况\n",
    "            if i == 4 and (distance[3] == distance[1]\n",
    "                           and distance[4] >= distance[2] - distance[0]):\n",
    "                return True\n",
    "\n",
    "            # 第 3 类路径交叉的情况\n",
    "            if i >= 5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3]\n",
    "                           and distance[i] >= distance[i - 2] - distance[i - 4]\n",
    "                           and distance[i - 2] > distance[i - 4]):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            # 第 1 类路径交叉的情况\n",
    "            if (distance[i] >= distance[i - 2]\n",
    "                    and distance[i - 1] <= distance[i - 3]):\n",
    "                return True\n",
    "\n",
    "            # 第 2 类路径交叉的情况\n",
    "            if i == 4 and (distance[3] == distance[1]\n",
    "                           and distance[4] >= distance[2] - distance[0]):\n",
    "                return True\n",
    "\n",
    "            # 第 3 类路径交叉的情况\n",
    "            if i >= 5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3]\n",
    "                           and distance[i] >= distance[i - 2] - distance[i - 4]\n",
    "                           and distance[i - 2] > distance[i - 4]):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "       \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, dis: List[int]) -> bool:\n",
    "        '''\n",
    "            所有的路径走法，都可以归纳为3种情况：\n",
    "                1、连续4步有交点\n",
    "                2、连续5步有交点\n",
    "                3、连续6步有交点\n",
    "            如果上述三种情况都走完了，还没交点，那就是没有交点的情况    \n",
    "        '''\n",
    "        n = len(dis)\n",
    "        if n <= 3: return False\n",
    "        for i in range(3, n):\n",
    "            # 1、连续4步\n",
    "            if dis[i] >= dis[i - 2] and dis[i - 1] <= dis[i - 3]:\n",
    "                return True\n",
    "            # 2、连续5步\n",
    "            if i >= 4 and dis[i - 1] == dis[i - 3] and dis[i] + dis[i - 4] >= dis[i - 2]:\n",
    "                return True\n",
    "            # 3、连续5步\n",
    "            if i >= 5 and dis[i - 2] >= dis[i - 4] and dis[i - 3] >= dis[i - 1] and dis[i - 1] + dis[i - 5] >= dis[i - 3] and dis[i] + dis[i - 4] >= dis[i - 2]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3,n):\n",
    "            if(distance[i] >= distance[i - 2] and distance[i - 1] <= distance[i - 3]):\n",
    "                return True;\n",
    "            if i == 4 and (distance[3] == distance[1] and distance[4] >= distance[2] - distance[0]):\n",
    "                return True;\n",
    "            if i >=5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3] and distance[i] >= distance[i - 2] - distance[i - 4] and distance[i - 2] > distance[i - 4]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "\n",
    "        def four(path):\n",
    "            return path[-1] >= path[-3] and path[-2] <= path[-4]\n",
    "\n",
    "        def five(path):\n",
    "            return path[-2] == path[-4] and path[-1] + path[-5] >= path[-3]\n",
    "\n",
    "        def six(path):\n",
    "            return path[-3] >= path[-5] and path[-2] <= path[-4] and path[-6] <= path[-4] and path[-1] + path[-5] >= path[-3] and path[-2] + path[\n",
    "                -6] >= path[-4]\n",
    "\n",
    "        for i, x in enumerate(distance):\n",
    "            if i >= 3:\n",
    "                if four(distance[i - 3:i + 1]):\n",
    "                    return True\n",
    "                if i >= 4:\n",
    "                    if five(distance[i - 4:i + 1]):\n",
    "                        return True\n",
    "                    if i >= 5:\n",
    "                        if six(distance[i - 5:i + 1]):\n",
    "                            return True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, d: List[int]) -> bool:\n",
    "        for i in range(len(d)):\n",
    "            if i+3<len(d) and d[i+3]>=d[i+1] and d[i+2]<=d[i]:\n",
    "                return (True)\n",
    "                break\n",
    "            elif i+4<len(d) and d[i+1]==d[i+3] and d[i+2]<=d[i]+d[i+4]:\n",
    "                return (True)\n",
    "                break\n",
    "            elif i+5<len(d) and d[i+1]+d[i+5]>=d[i+3] and d[i+1]<d[i+3] and d[i+2]<=d[i]+d[i+4] and d[i+2]>d[i+4]:\n",
    "                return (True)\n",
    "                break\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, x: List[int]) -> bool:\n",
    "        n = len(x)\n",
    "        if n < 4:\n",
    "            return False\n",
    "        for i in range(3, n):\n",
    "            if x[i] >= x[i - 2] and x[i - 1] <= x[i - 3]:\n",
    "                return True\n",
    "            if i > 3 and x[i - 1] == x[i - 3] and x[i] + x[i - 4] == x[i - 2]:\n",
    "                return True\n",
    "            if i > 4 and x[i] + x[i - 4] >= x[i - 2] and x[i - 1] >= x[i - 3] - x[i - 5] \\\n",
    "                and x[i - 1] <= x[i - 3] and x[i - 2] >= x[i - 4] and x[i - 3] >= x[i - 5]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            # 第 1 类路径交叉的情况\n",
    "            if (distance[i] >= distance[i - 2]\n",
    "                    and distance[i - 1] <= distance[i - 3]):\n",
    "                return True\n",
    "\n",
    "            # 第 2 类路径交叉的情况\n",
    "            if i == 4 and (distance[3] == distance[1]\n",
    "                           and distance[4] >= distance[2] - distance[0]):\n",
    "                return True\n",
    "\n",
    "            # 第 3 类路径交叉的情况\n",
    "            if i >= 5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3]\n",
    "                           and distance[i] >= distance[i - 2] - distance[i - 4]\n",
    "                           and distance[i - 2] > distance[i - 4]):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            if distance[i]>=distance[i-2] and distance[i-1]<=distance[i-3]:\n",
    "                return True\n",
    "            if i==4 and distance[1]==distance[3] and distance[4]>=distance[2]-distance[0]:\n",
    "                return True\n",
    "            if i>=5 and distance[i-2]>distance[i-4] and distance[i-1]<distance[i-3] and distance[i-1]>=distance[i-3]-distance[i-5] and distance[i]>=distance[i-2]-distance[i-4]:\n",
    "                return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        if len(distance) < 4:\n",
    "            return False\n",
    "        \n",
    "        n = len(distance)\n",
    "\n",
    "        for i in range(3, n):\n",
    "\n",
    "            if distance[i] >= distance[i - 2] and distance[i - 1] <= distance[i - 3]:\n",
    "                return True\n",
    "\n",
    "            if i == 4 and distance[3] == distance[1] and distance[4] >= distance[2] - distance[0]:\n",
    "                return True\n",
    "            \n",
    "            if i >= 5 and distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3] and distance[i] >= distance[i - 2] - distance[i - 4] and distance[i - 2] > distance[i - 4]:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "\n",
    "        # 处理第 1 种情况\n",
    "        i = 0\n",
    "        while i < n and (i < 2 or distance[i] > distance[i - 2]):\n",
    "            i += 1\n",
    "\n",
    "        if i == n:\n",
    "            return False\n",
    "\n",
    "        # 处理第 j 次移动的情况\n",
    "        if ((i == 3 and distance[i] == distance[i - 2])\n",
    "                or (i >= 4 and distance[i] >= distance[i - 2] - distance[i - 4])):\n",
    "            distance[i - 1] -= distance[i - 3]\n",
    "        i += 1\n",
    "\n",
    "        # 处理第 2 种情况\n",
    "        while i < n and distance[i] < distance[i - 2]:\n",
    "            i += 1\n",
    "\n",
    "        return i != n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            if(distance[i] >= distance[i-2]) and (distance[i-1] <= distance[i-3]):\n",
    "                return True\n",
    "\n",
    "            if i == 4 and (distance[3] == distance[1] and distance[4] >= distance[2] - distance[0]):\n",
    "                return True\n",
    "\n",
    "            if i >= 5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3]\n",
    "                            and distance[i] >= distance[i - 2] - distance[i - 4]\n",
    "                            and distance[i - 2] > distance[i - 4]):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            # 第 1 类路径交叉的情况\n",
    "            if (distance[i] >= distance[i - 2]\n",
    "                    and distance[i - 1] <= distance[i - 3]):\n",
    "                return True\n",
    "\n",
    "            # 第 2 类路径交叉的情况\n",
    "            if i == 4 and (distance[3] == distance[1]\n",
    "                           and distance[4] >= distance[2] - distance[0]):\n",
    "                return True\n",
    "\n",
    "            # 第 3 类路径交叉的情况\n",
    "            if i >= 5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3]\n",
    "                           and distance[i] >= distance[i - 2] - distance[i - 4]\n",
    "                           and distance[i - 2] > distance[i - 4]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            if distance[i] >= distance[i - 2] and distance[i - 1] <= distance[i - 3]:\n",
    "                return True\n",
    "            if i == 4 and distance[3] == distance[1] and distance[4] >= distance[2] - distance[0]:\n",
    "                return True\n",
    "            if i >= 5 and distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3] and distance[i] >= distance[i - 2] - distance[i - 4] and distance[i - 2] > distance[i - 4]:\n",
    "                return True\n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(distance):\n",
    "    lst = []\n",
    "    for v in distance:\n",
    "        # lst里不满三个，直接添\n",
    "        if len(lst) < 3:\n",
    "            lst.append(v)\n",
    "            continue\n",
    "\n",
    "        # lst里有4个，来了第五个\n",
    "        if len(lst) == 4:\n",
    "            a, b, c, d = lst\n",
    "            if d == b and v == c-a:\n",
    "                return True\n",
    "            assert d >= b and c > a\n",
    "            # 三种情况\n",
    "            # 第一种 newp < c-a\n",
    "            if v < c-a:\n",
    "                # 把a,b删掉，已经没用了\n",
    "                lst = [c, d, v]\n",
    "            elif v <= c:\n",
    "                # 把d修改，c不变，前两个删除\n",
    "                lst = [c, d-b, v]\n",
    "            # newp > c\n",
    "            else:\n",
    "                # 把a删掉\n",
    "                lst = [b, c, d, v]\n",
    "            continue\n",
    "\n",
    "        assert len(lst) == 3\n",
    "        # lst里面有三个，现在来了第4个\n",
    "        a, b, c = lst\n",
    "        d = v\n",
    "        # 判断这一轮是否相交\n",
    "        if c <= a and d >= b:\n",
    "            return True\n",
    "        # 终点在a左边，a已经没用了\n",
    "        if d < b:\n",
    "            lst = [b, c, d]\n",
    "            continue\n",
    "        # 终点在a右边，d>=b\n",
    "        lst.append(d)\n",
    "    return False\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        return func1(distance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        #  time: O(n)\n",
    "        # space: O(1)\n",
    "        \n",
    "        n = len(distance)\n",
    "        for i in range(n-3):\n",
    "            a, b, c, d = distance[i], distance[i+1], distance[i+2], distance[i+3]    # 考虑 a 段被 cross 的三种情况：从左侧、从下端、从右侧\n",
    "            if d < b:\n",
    "                continue\n",
    "            if c <= a:                                                               # 从左侧交叉到 a 段\n",
    "                return True\n",
    "            if i + 4 < n:\n",
    "                e = distance[i+4]\n",
    "                if d == b and e == c-a:                                              # 从下端交叉到 a 段\n",
    "                    return True\n",
    "            if i + 5 < n:\n",
    "                e, f = distance[i+4], distance[i+5]\n",
    "                if c-a <= e <= c and f >= d-b:                                       # 从右侧交叉到 a 段\n",
    "                    return True\n",
    "        return False\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            # 第 1 类路径交叉的情况\n",
    "            if (distance[i] >= distance[i - 2]\n",
    "                    and distance[i - 1] <= distance[i - 3]):\n",
    "                return True\n",
    "\n",
    "            # 第 2 类路径交叉的情况\n",
    "            if i == 4 and (distance[3] == distance[1]\n",
    "                           and distance[4] >= distance[2] - distance[0]):\n",
    "                return True\n",
    "\n",
    "            # 第 3 类路径交叉的情况\n",
    "            if i >= 5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3]\n",
    "                           and distance[i] >= distance[i - 2] - distance[i - 4]\n",
    "                           and distance[i - 2] > distance[i - 4]):\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        ''' 状态机100ms\n",
    "        ld = len(distance)\n",
    "        if ld < 4:\n",
    "            return False\n",
    "        state = 1\n",
    "        for i in range(2, ld):\n",
    "            print(state)\n",
    "            if state == 1:\n",
    "                if distance[i] == distance[i - 2]:\n",
    "                    state = 3\n",
    "                elif distance[i] < distance[i - 2]:\n",
    "                    state = 2\n",
    "            else:\n",
    "                if distance[i] >= distance[i - 2]:\n",
    "                    return True\n",
    "                if state == 3:\n",
    "                    if i > 3 and distance[i - 4] + distance[i] >= distance[i - 2]:\n",
    "                        return True\n",
    "                    state = 2\n",
    "                elif i > 4 and distance[i - 4] + distance[i] >= distance[i - 2] and distance[i - 5] + distance[i - 1] >= distance[i - 3] and distance[i - 2] >= distance[i - 4]:\n",
    "                    return True\n",
    "        return False\n",
    "        '''\n",
    "        # 分类讨论不相交的情况\n",
    "        # 1、一直外卷\n",
    "        i, ld = 2, len(distance)\n",
    "        if ld < 4:\n",
    "            return False\n",
    "        while i < ld and distance[i] > distance[i - 2]:\n",
    "            i += 1\n",
    "        if i == ld:\n",
    "            return False\n",
    "        # 2、外卷转内卷，如果开始卷的第一条有可能与前面的相交，则需要缩短允许的长度\n",
    "        m = distance[i - 2]\n",
    "        if i >= 4:\n",
    "            m -= distance[i - 4]\n",
    "        if distance[i] >= m and i >= 3:\n",
    "            distance[i - 1] -= distance[i - 3]\n",
    "        # 3、内卷\n",
    "        i += 1\n",
    "        while i < ld and distance[i] < distance[i - 2]:\n",
    "            i += 1\n",
    "        return i != ld"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        lst = []\n",
    "        n = len(distance)\n",
    "        for i in range(n):\n",
    "            if i < 3:\n",
    "                lst.append(distance[i])\n",
    "                continue\n",
    "            if len(lst) == 3:\n",
    "                a,b,c = lst[-3:]\n",
    "                if c <= a:\n",
    "                    if distance[i] >= b:\n",
    "                        return True\n",
    "                    lst.pop(0)\n",
    "                lst.append(distance[i])\n",
    "                continue\n",
    "            elif len(lst) == 4:\n",
    "                a,b,c,d = lst\n",
    "                if d < b:\n",
    "                    if distance[i] >= c:\n",
    "                        return True\n",
    "                    lst = [c,d,distance[i]]\n",
    "                elif d == b:\n",
    "                    if distance[i] >= c-a:\n",
    "                        return True\n",
    "                    lst = [c,d,distance[i]]\n",
    "                else:\n",
    "                    if distance[i] < c-a:\n",
    "                        lst = [c, d, distance[i]]\n",
    "                    else:\n",
    "                        lst.append(distance[i])\n",
    "                continue\n",
    "            elif len(lst) == 5:\n",
    "                a,b,c,d,e = lst\n",
    "                if e < c-a:\n",
    "                    if distance[i] >= d:\n",
    "                        return True\n",
    "                    lst = [c, d, e,distance[i]]\n",
    "                elif e == c-a:\n",
    "                    if distance[i] >= d-b:\n",
    "                        return True\n",
    "                    lst = [d,e,distance[i]]\n",
    "                elif c-a < e <= c:\n",
    "                    if distance[i] >= d-b:\n",
    "                        return True\n",
    "                    lst = [c,d-b,e,distance[i]]\n",
    "                else:\n",
    "                    lst = [b,c,d,e,distance[i]]\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        lst = []\n",
    "        n = len(distance)\n",
    "        for i in range(n):\n",
    "            if i < 3:\n",
    "                lst.append(distance[i])\n",
    "                continue\n",
    "            if len(lst) == 3:\n",
    "                a,b,c = lst[-3:]\n",
    "                if c <= a:\n",
    "                    if distance[i] >= b:\n",
    "                        return True\n",
    "                    lst.pop(0)\n",
    "                lst.append(distance[i])\n",
    "                continue\n",
    "            elif len(lst) == 4:\n",
    "                a,b,c,d = lst\n",
    "                if d < b:\n",
    "                    if distance[i] >= c:\n",
    "                        return True\n",
    "                    lst = [b,c,d,distance[i]]\n",
    "                elif d == b:\n",
    "                    if distance[i] >= c-a:\n",
    "                        return True\n",
    "                    lst = [c,d,distance[i]]\n",
    "                else:\n",
    "                    if distance[i] < c-a:\n",
    "                        lst = [c, d, distance[i]]\n",
    "                    else:\n",
    "                        lst.append(distance[i])\n",
    "                continue\n",
    "            elif len(lst) == 5:\n",
    "                a,b,c,d,e = lst\n",
    "                if e < c-a:\n",
    "                    if distance[i] >= d:\n",
    "                        return True\n",
    "                    lst = [c, d, e,distance[i]]\n",
    "                elif e == c-a:\n",
    "                    if distance[i] >= d-b:\n",
    "                        return True\n",
    "                    lst = [d,e,distance[i]]\n",
    "                elif c-a < e <= c:\n",
    "                    if distance[i] >= d-b:\n",
    "                        return True\n",
    "                    lst = [c,d-b,e,distance[i]]\n",
    "                else:\n",
    "                    lst = [b,c,d,e,distance[i]]\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        N = len(distance)\n",
    "        if N <= 3: return False\n",
    "        x,y = -distance[1], distance[0]-distance[2]\n",
    "        lim = [0,0,distance[0],x,0] # B,R,U,L\n",
    "        inner = y >= 0\n",
    "        for i in range(3,N):\n",
    "            if i & 1: x += distance[i]*(i%4-2)\n",
    "            else: y += distance[i]*(1-i%4)\n",
    "            if inner:\n",
    "                if ((x if i&1 else y)-lim[(i+2)%4])*((i+1)%4-1.5) <= 0: return True\n",
    "            else:\n",
    "                if ((x if i&1 else y)-lim[(i+2)%4])*((i+1)%4-1.5) >= 0:\n",
    "                    if ((x if i&1 else y)-lim[4])*((i+1)%4-1.5) <= 0: lim[(i-1)%4] = lim[(i+1)%4]\n",
    "                    inner = True\n",
    "                    lim.pop(-1)\n",
    "                else: lim[4] = lim[(i+1)%4]\n",
    "            lim[(i+1)%4] = y if i&1 else x\n",
    "            #print(i,':',x,y,lim)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            # 第 1 类路径交叉的情况\n",
    "            if (distance[i] >= distance[i - 2]\n",
    "                    and distance[i - 1] <= distance[i - 3]):\n",
    "                return True\n",
    "\n",
    "            # 第 2 类路径交叉的情况\n",
    "            if i == 4 and (distance[3] == distance[1]\n",
    "                           and distance[4] >= distance[2] - distance[0]):\n",
    "                return True\n",
    "\n",
    "            # 第 3 类路径交叉的情况\n",
    "            if i >= 5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3]\n",
    "                           and distance[i] >= distance[i - 2] - distance[i - 4]\n",
    "                           and distance[i - 2] > distance[i - 4]):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    # solve 2\n",
    "    def isSelfCrossing2(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "\n",
    "        # 处理第 1 种情况\n",
    "        i = 0\n",
    "        while i < n and (i < 2 or distance[i] > distance[i - 2]):\n",
    "            i += 1\n",
    "\n",
    "        if i == n:\n",
    "            return False\n",
    "\n",
    "        # 处理第 j 次移动的情况\n",
    "        if ((i == 3 and distance[i] == distance[i - 2])\n",
    "                or (i >= 4 and distance[i] >= distance[i - 2] - distance[i - 4])):\n",
    "            distance[i - 1] -= distance[i - 3]\n",
    "        i += 1\n",
    "\n",
    "        # 处理第 2 种情况\n",
    "        while i < n and distance[i] < distance[i - 2]:\n",
    "            i += 1\n",
    "\n",
    "        return i != n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            # 第 1 类路径交叉的情况\n",
    "            if (distance[i] >= distance[i - 2]\n",
    "                    and distance[i - 1] <= distance[i - 3]):\n",
    "                return True\n",
    "\n",
    "            # 第 2 类路径交叉的情况\n",
    "            if i == 4 and (distance[3] == distance[1]\n",
    "                           and distance[4] >= distance[2] - distance[0]):\n",
    "                return True\n",
    "\n",
    "            # 第 3 类路径交叉的情况\n",
    "            if i >= 5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3]\n",
    "                           and distance[i] >= distance[i - 2] - distance[i - 4]\n",
    "                           and distance[i - 2] > distance[i - 4]):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        if len(distance)<=3:\n",
    "            return False\n",
    "        for i in range(len(distance)):\n",
    "            if i>=3:\n",
    "                if distance[i-1]<=distance[i-3] and distance[i]>=distance[i-2]:\n",
    "                    return True\n",
    "            if i>=4:\n",
    "                if distance[i]+distance[i-4]>=distance[i-2] and distance[i-1]==distance[i-3]:\n",
    "                    return True\n",
    "            if i>=5:\n",
    "                if distance[i-1]+distance[i-5]>=distance[i-3] and distance[i]+distance[i-4]>=distance[i-2]>=distance[i-4]:\n",
    "                    if not distance[i-1]>distance[i-3]:\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, dis: List[int]) -> bool:\n",
    "        '''\n",
    "            所有的路径走法，都可以归纳为3种情况：\n",
    "                1、连续4步有交点\n",
    "                2、连续5步有交点\n",
    "                3、连续6步有交点\n",
    "            如果上述三种情况都走完了，还没交点，那就是没有交点的情况    \n",
    "        '''\n",
    "        n = len(dis)\n",
    "        if n <= 3: return False\n",
    "        for i in range(3, n):\n",
    "            # 1、连续4步\n",
    "            if dis[i] >= dis[i - 2] and dis[i - 1] <= dis[i - 3]:\n",
    "                return True\n",
    "            # 2、连续5步。也就是 第i条边 与 第i-4条边重合\n",
    "            if i >= 4 and dis[i - 1] == dis[i - 3] and dis[i] + dis[i - 4] >= dis[i - 2]:\n",
    "                return True\n",
    "            # 3、连续6步\n",
    "            if i >= 5 and dis[i - 2] >= dis[i - 4] and dis[i - 3] >= dis[i - 1] and dis[i - 1] + dis[i - 5] >= dis[i - 3] and dis[i] + dis[i - 4] >= dis[i - 2]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            # 第 1 类路径交叉的情况\n",
    "            if (distance[i] >= distance[i - 2]\n",
    "                    and distance[i - 1] <= distance[i - 3]):\n",
    "                return True\n",
    "\n",
    "            # 第 2 类路径交叉的情况\n",
    "            if i == 4 and (distance[3] == distance[1]\n",
    "                           and distance[4] >= distance[2] - distance[0]):\n",
    "                return True\n",
    "\n",
    "            # 第 3 类路径交叉的情况\n",
    "            if i >= 5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3]\n",
    "                           and distance[i] >= distance[i - 2] - distance[i - 4]\n",
    "                           and distance[i - 2] > distance[i - 4]):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            # 第 1 类路径交叉的情况\n",
    "            if (distance[i] >= distance[i - 2]\n",
    "                    and distance[i - 1] <= distance[i - 3]):\n",
    "                return True\n",
    "\n",
    "            # 第 2 类路径交叉的情况\n",
    "            if i == 4 and (distance[3] == distance[1]\n",
    "                           and distance[4] >= distance[2] - distance[0]):\n",
    "                return True\n",
    "\n",
    "            # 第 3 类路径交叉的情况\n",
    "            if i >= 5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3]\n",
    "                           and distance[i] >= distance[i - 2] - distance[i - 4]\n",
    "                           and distance[i - 2] > distance[i - 4]):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        N = len(distance)\n",
    "        if N <= 3: return False\n",
    "        x,y = -distance[1], distance[0]-distance[2]\n",
    "        lim = [0,0,distance[0],x,0] # B,R,U,L\n",
    "        inner = y >= 0\n",
    "        r0,r1,r2,r3 = 3,0,1,2\n",
    "        sign = -1\n",
    "        i = 3\n",
    "        while i < N:\n",
    "            if i & 1: x += distance[i]*(r0-2)\n",
    "            else: y += distance[i]*(1-r0)\n",
    "            w = ((x if i&1 else y)-lim[r2])*(r1-1.5)\n",
    "            if inner:\n",
    "                if w <= 0: return True\n",
    "            elif w >= 0:\n",
    "                if ((x if i&1 else y)-lim[4])*(r1-1.5) <= 0: lim[r3] = lim[r1]\n",
    "                inner = True\n",
    "                lim.pop(-1)\n",
    "            else: lim[4] = lim[r1]\n",
    "            lim[r1] = y if i&1 else x\n",
    "            r0,r1,r2,r3 = r1,r2,r3,r0\n",
    "            if r1 == 2 or r1 == 0: sign = -sign\n",
    "            i += 1\n",
    "            #print(i,':',x,y,lim)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        for i in range(3, n):\n",
    "            if (distance[i-1]<=distance[i-3] \n",
    "                    and distance[i]>=distance[i-2]):\n",
    "                return True\n",
    "            if (i>=4 and distance[i-1]==distance[i-3]\n",
    "                and distance[i-2]<=distance[i]+distance[i-4]):\n",
    "                return True\n",
    "            if (i>=5 and distance[i-2]>=distance[i-4]\n",
    "                and distance[i]>=distance[i-2]-distance[i-4]\n",
    "                and distance[i-3]>=distance[i-5]\n",
    "                and distance[i-3]>=distance[i-1]\n",
    "                and distance[i-3]<=distance[i-5]+distance[i-1]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        n = len(distance)\n",
    "        if n < 4: return False\n",
    "\n",
    "        # 先判断是否一直外旋\n",
    "        i = 2\n",
    "        while i < n and distance[i] > distance[i-2]:\n",
    "            i += 1\n",
    "        if i == n: return False\n",
    "\n",
    "        # 外旋->内旋\n",
    "        if (i >= 4 and distance[i] >= distance[i-2] - distance[i-4]) or (i == 3 and distance[i] == distance[i-2]): \n",
    "            distance[i-1] -= distance[i-3]\n",
    "\n",
    "        # 判断是否一直内旋\n",
    "        i += 1\n",
    "        while i < n and distance[i] < distance[i-2]:\n",
    "            i += 1\n",
    "        \n",
    "        return i != n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        lst = []\n",
    "        n = len(distance)\n",
    "        for i in range(n):\n",
    "            if i < 3:\n",
    "                lst.append(distance[i])\n",
    "                continue\n",
    "            if len(lst) == 3:\n",
    "                a,b,c = lst[-3:]\n",
    "                if c <= a:\n",
    "                    if distance[i] >= b:\n",
    "                        return True\n",
    "                    lst.pop(0)\n",
    "                lst.append(distance[i])\n",
    "                continue\n",
    "            elif len(lst) == 4:\n",
    "                a,b,c,d = lst\n",
    "                if d < b:\n",
    "                    if distance[i] >= c:\n",
    "                        return True\n",
    "                    lst = [c,d,distance[i]]\n",
    "                elif d == b:\n",
    "                    if distance[i] >= c-a:\n",
    "                        return True\n",
    "                    lst = [c,d,distance[i]]\n",
    "                else:\n",
    "                    if distance[i] < c-a:\n",
    "                        lst = [c, d, distance[i]]\n",
    "                    else:\n",
    "                        lst.append(distance[i])\n",
    "                continue\n",
    "            elif len(lst) == 5:\n",
    "                a,b,c,d,e = lst\n",
    "                if e < c-a:\n",
    "                    if distance[i] >= d:\n",
    "                        return True\n",
    "                    lst = [c, d, e,distance[i]]\n",
    "                elif e == c-a:\n",
    "                    if distance[i] >= d-b:\n",
    "                        return True\n",
    "                    lst = [d,e,distance[i]]\n",
    "                elif c-a < e <= c:\n",
    "                    if distance[i] >= d-b:\n",
    "                        return True\n",
    "                    lst = [c,d-b,e,distance[i]]\n",
    "                else:\n",
    "                    lst = [b,c,d,e,distance[i]]\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        ld = len(distance)\n",
    "        if ld < 4:\n",
    "            return False\n",
    "        state = 1\n",
    "        for i in range(2, ld):\n",
    "            print(state)\n",
    "            if state == 1:\n",
    "                if distance[i] == distance[i - 2]:\n",
    "                    state = 3\n",
    "                elif distance[i] < distance[i - 2]:\n",
    "                    state = 2\n",
    "            else:\n",
    "                if distance[i] >= distance[i - 2]:\n",
    "                    return True\n",
    "                if state == 3:\n",
    "                    if i > 3 and distance[i - 4] + distance[i] >= distance[i - 2]:\n",
    "                        return True\n",
    "                    state = 2\n",
    "                elif i > 4 and distance[i - 4] + distance[i] >= distance[i - 2] and distance[i - 5] + distance[i - 1] >= distance[i - 3] and distance[i - 2] >= distance[i - 4]:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        ld = len(distance)\n",
    "        if ld < 4:\n",
    "            return False\n",
    "        state = 1\n",
    "        for i in range(2, ld):\n",
    "            print(state)\n",
    "            if state == 1:\n",
    "                if distance[i] == distance[i - 2]:\n",
    "                    state = 3\n",
    "                elif distance[i] < distance[i - 2]:\n",
    "                    state = 2\n",
    "            else:\n",
    "                if distance[i] >= distance[i - 2]:\n",
    "                    return True\n",
    "                if state == 3:\n",
    "                    if i > 3 and distance[i - 4] + distance[i] >= distance[i - 2]:\n",
    "                        return True\n",
    "                    state = 2\n",
    "                elif i > 4 and distance[i - 4] + distance[i] >= distance[i - 2] and distance[i - 5] + distance[i - 1] >= distance[i - 3] and distance[i - 2] >= distance[i - 4]:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSelfCrossing(self, distance: List[int]) -> bool:\n",
    "        distance = [0] + distance\n",
    "        n = len(distance)\n",
    "\n",
    "        for d in range(3, n):\n",
    "            d_1 = distance[d-1]\n",
    "            d_3 = distance[d-3]\n",
    "            d_0 = distance[d]\n",
    "            d_2 = distance[d-2]\n",
    "            if d_1<=d_3 and d_0 >= d_2:\n",
    "                print(1)\n",
    "                return True\n",
    "            \n",
    "            if d<5:\n",
    "                continue\n",
    "            d_5 = distance[d-5]\n",
    "            d_4 = distance[d-4]\n",
    "            if d_1 <= d_3 and d_1+d_5>=d_3 and d_2>d_4 and d_2 <= d_0+d_4:\n",
    "                print(2)\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
